package com.lishem.carl._10dp;

/**
 * https://leetcode.cn/problems/delete-operation-for-two-strings/description/
 * <p>
 * 给定两个单词word1和word2，返回使得word1和word2相同所需的最小步数。
 * <p>
 * 每步可以删除任意一个字符串中的一个字符。
 * <p>
 * 示例 1：
 * <p>
 * 输入: word1 = "sea", word2 = "eat"
 * <p>
 * 输出: 2
 * <p>
 * 解释: 第一步将 "sea" 变为 "ea" ，第二步将 "eat "变为 "ea"
 * <p>
 * 示例  2:
 * <p>
 * 输入：word1 = "leetcode", word2 = "etco"
 * <p>
 * 输出：4
 */
public class _36LetCode583_两个字符串的删除操作 {

    public int minDistance(String word1, String word2) {
        char[] chars1 = word1.toCharArray();
        char[] chars2 = word2.toCharArray();
        int[][] dp = new int[chars1.length + 1][chars2.length + 1];
        for (int i = 1; i <= chars1.length; i++) {
            for (int j = 1; j <= chars2.length; j++) {
                if (chars1[i - 1] == chars2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        return chars1.length + chars2.length - 2 * dp[chars1.length][chars2.length];
    }

    public static void main(String[] args) {
        _36LetCode583_两个字符串的删除操作 sol = new _36LetCode583_两个字符串的删除操作();
        System.out.println(sol.minDistance("sea", "eat"));
        System.out.println(sol.minDistance("leetcode", "etco"));
    }
}
